Solupals - Textbook Solutions Solutions Data Structures and Java Collection Framework - William Collins -3rd Ed


10.12 The following program generates a BinarySearchTree object of n elements. Draw the tree when
n = 13. For any n ≥ 0, provide a ! (that is, Big Thet
a) estimate of height(n), that is, the height of the
BinarySearchTree object as a function of n.
import java.util.*;
public class weirdBST
{
public static void main (String[] args)
{
new weirdBST().run();
} // method main
public void run()
{
BinarySearchTree tree = new BinarySearchTree();
LinkedList list =new LinkedList();
System.out.println ("Enter n > 0");
int n = new Scanner (System.in).nextInt();
tree.add (1.0);
list.add (1.0);
int k = 2;
while (tree.size() < n)
addLevel (tree, n, k++, list);
System.out.println (tree.height());
} // method run
public void addLevel (BinarySearchTree tree, int n, int k,
LinkedList list)
{
final double SMALL = 0.00000000001;
LinkedList newList = new LinkedList();
Iterator itr = list.iterator();
double d = itr.next();
tree.add (d - 1.0);
newList.add (d - 1.0);
for (int i = 0; i < k && tree.size() < n; i++)
{
tree.add (d + SMALL );
newList.add (d + SMALL);
if (itr.hasNext())
d = itr.next();
} // for
list.clear();
list.addAll (newList);
} // method addLevel
} // class weirdBST

 
 
View Solution
 
 
 
<< Back